package com.lzhsite.leetcode.algoritom
/**
 * 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，
 * 使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
 *
 * 这个问题和之前的问题Leetcode 15:三数之和类似。
 * 我们首先想到的是通过对撞指针的方法来解这个问题。我们先要对nums排序，接着建立l和r两个指针，然后我们遍历nums
 *
 * 我们要将left=i+1、right=len(nums)-1这样初始化，因为我们希望在[l:r]中进行寻找操作。
 * 计算sum=nums[i]+nums[left]+nums[right]和target的差是多少，并且我们要记录下来，最后取最小的差对应的sum作为结果。
 * 当left<right的时候，我们就要对窗口进行缩放操作。如果sum<target的话，我们就要将l++，以寻找更大的sum；否则的话，
 * 我们将right--，以寻找更小的sum。当本次操作结束后，我们就要进入下一轮循环
 */
object LeetCode016接近三数之和 {

  def threeSumClosest(nums: Array[Int], target: Int): Int = {
    val sortArr = nums.sorted
    var closeResult = Int.MaxValue
    var tempResult = 0
    var ansResult = 0
    
    //for(i <- 1 to nums_len - 3):
    //for i in range(nums_len - 2):
    for (i <- 0 until sortArr.length - 2) {
      var left = i + 1
      var right = sortArr.length - 1
      while (left < right) {
        //println("iCur: "+iCur)
        //println("left: "+left)
        //println("right: "+right)
        //println("Sum: "+(sortArr(i) + sortArr(left)+sortArr(right)))
        var arrSum = sortArr(i) + sortArr(left) + sortArr(right)
        arrSum match {
          case sum if sum < target => { tempResult = target - arrSum; left += 1; if (tempResult < closeResult) { ansResult = arrSum; closeResult = tempResult } }
          case sum if sum > target => { tempResult = arrSum - target; right -= 1; if (tempResult < closeResult) { ansResult = arrSum; closeResult = tempResult } }
          case sum if sum == target => return sum
        }

      }
    }
    return ansResult
  }
  
/**  我们实际上可一对上面这个问题进行剪枝操作。
 * 我们首先将nums排序，然后遍历nums中的每个元素num。我们判断nums中最大的两个数加上num后是不是小于target，
 * 如果是的话，此时我们没有办法找比这三个更小的和了，我们就要建立一个result数组，将它们的和加入。
 * 我们判断nums中最小的两个数加上num后是不是大于target，如果是的话，此时我们没有办法找比这三个更大的和了，
 * 我们就要将它们的和加入到result中。上述这两步操作是剪枝操作。
 * 然后对于其他的情况，我们再按照之前的思路处理即可，但是此时我们直接将和加入result中，而没有对最小距离单独处理。
 * 最后我们只要取和target最近的值即可（将此策略添加到sort函数中
 * */
  def threeSumClosest2(nums: Array[Int], target: Int): Int = {
 
    val sortArr = nums.sorted
    var closeResult = Int.MaxValue
    var tempResult = 0
    var ansResult = 0
    
    //for(i <- 1 to nums_len - 3):
    //for i in range(nums_len - 2):
    for (i <- 0 until sortArr.length - 2) {
      var left = i + 1
      var right = sortArr.length - 1
 
     var leftSum = sortArr(left) +sortArr(left + 1) +  sortArr(i)
     var rightSum =  sortArr(right) + sortArr(right - 1) + sortArr(i)
      
     if  (leftSum > target)
        if (tempResult < closeResult) { ansResult = leftSum; closeResult = tempResult } 
      else if (rightSum < target)
        if (tempResult < closeResult) { ansResult = rightSum; closeResult = tempResult } 
     
     
      while (left < right) {
       
        var arrSum = sortArr(i) + sortArr(left) + sortArr(right)
        arrSum match {
          case sum if sum < target => { tempResult = target - arrSum; left += 1; if (tempResult < closeResult) { ansResult = arrSum; closeResult = tempResult } }
          case sum if sum > target => { tempResult = arrSum - target; right -= 1; if (tempResult < closeResult) { ansResult = arrSum; closeResult = tempResult } }
          case sum if sum == target => return sum
        }

      }
    }
    return ansResult
  }
  
  def main(args: Array[String]) {
    var target = 1
    var nums = Array(-1, 2, 1, -4)
    println(threeSumClosest2(nums, target));
  }
  
  // 默认scala的List是可不变的，值一旦被定义了就不能改变了，所以列表改变后都需要重新赋值。
  // 不支持随机访问
}